package com.str.array;
public class Searching {

  private static final int NONE = -1;
 
  public static int linearSearch1(Object[] a, 
      int left, int right, Object val) {
  	for (int i = left; i <= right; i++)
      if (val.equals(a[i]))
        return i;
    return NONE;
  }
  
  public static int linearSearch2(Comparable[] a,
      int left, int right, Comparable val) {
    for (int i = left; i <= right; i++) {
      int comp = val.compareTo(a[i]);
      if (comp == 0)
        return i;
      else if (comp < 0)
        break;
    }
    return NONE;
  }
  
  public static int binarySearch(Comparable[] a,
      int left, int right, Comparable val) {
  	int l = left, r = right;
    while (l <= r) {
      int m = (l + r) / 2;
      int comp = val.compareTo(a[m]);
	  if (comp == 0) return m;
	  else if (comp < 0)  r = m - 1;
	  else l = m + 1;
    }
    return NONE;
  }

  public static void main(String[] args) {
    String[] word1 = {"dog", "cat", "rat", "pig", "fox", "eel"};
    int left1 = 0, right1 = word1.length - 1;
    
    String[] word2 = {"cat", "dog", "eel", "fox", "pig", "rat"};
    int left2 = 0, right2 = word2.length - 1;
    
    String[] testcases = {"ant", "bat", "cat", "dog", "eel", 
        "fox", "hen", "pig", "rat"};   
    for (int t = 0; t < testcases.length; t++) {
      String target = testcases[t];
      System.out.println(target
        + "  " + linearSearch1(word1, left1, right1, target)
        + "  " + linearSearch2(word2, left2, right2, target)
        + "  " + binarySearch(word2, left2, right2, target));
    }
  }
}
